package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;

import sun.tools.jar.resources.jar;
import util.LogUtils;

/*
 * 
原题　
	Invert a binary tree.
	
	     4
	   /   \
	  2     7
	 / \   / \
	1   3 6   9
	to
	     4
	   /   \
	  7     2
	 / \   / \
	9   6 3   1
	Trivia:
	This problem was inspired by this original tweet by Max Howell:
	Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.
题目大意
	反转二叉树
解题思路
	
 * @Date 2017-09-14 23：12
 */
public class _226_Invert_Binary_Tree {
	
	public class TreeNode {
	    int val;
	    TreeNode left;
	    TreeNode right;
	    TreeNode(int x) { val = x; }
	    public TreeNode(int x, TreeNode l, TreeNode r) {val = x; left = l; right = r;}
	}
	
	/**
	 * 反转二叉树
	 * @My:我就是厉害！！！！！！！！！！！！！！！！！
	 * @param node
	 * @return
	 */
    public TreeNode invertTree(TreeNode node) {
    	if (node == null)	return null;		//事实上只要return就好了
    	exchange(node);
    	invertTree(node.left);
    	invertTree(node.right);
    	return node;
    }
    
    public void exchange(TreeNode node) {
    	TreeNode t = node.left;
    	node.left = node.right;
    	node.right = t;
    }
	
    public void traverse(TreeNode node) {
    	if (node == null)	return;
    	
    	traverse(node.left);
    	LogUtils.print(node.val);

      	traverse(node.right);
    }
    
	private TreeNode newTree1() {
		return new TreeNode(4, 
					new TreeNode(2, 
							new TreeNode(1, null, null),  
							new TreeNode(3, null, null)
					), 
					new TreeNode(7, 
							new TreeNode(6, null, null),  
							new TreeNode(9, null, null))
				);
	}
	
    
	public static void main(String[] args) {
		_226_Invert_Binary_Tree obj = new _226_Invert_Binary_Tree();
		obj.invertTree(obj.newTree1());
	}

}
